package com.algrithom.graph.mincreatetree;

/**
 * @author think
 * @since 2020/3/8
 */
public class UnionFind {
    
    private final int[] parent;
    
    public UnionFind(int capacity){
        parent = new int[capacity];
        // 初始化parent数组，让各个元素的父节点指向自身,表面其自身已经是根节点
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }
    
    public boolean find(int x,int y){
        // 根节点相同
        return find(x) == find(y);
    }
    
    private int find(int x){
        if (x == parent[x]) {
            return x;
        }
        // 路径压缩，在寻找根节点的过程中不断地将节点的父节点往上挪，最后形成两层
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void union(int x,int y){
        if (find(x) == find(y)) {
            return;
        }
        parent[find(x)] = find(y);
    }
}
